package com.kabuda.hot100.普通数组.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @author kabuda
 * @create 2025-02-04 11:31
 * <p>
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 * <p>
 * 示例 1：
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 */
public class t56_合并区间 {
    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(merge(new int[][]{{1, 4}, {0,2}, {3, 5}})));
    }

    public static int[][] merge(int[][] intervals) {
        //从开始值进行排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        //Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        ArrayList<int[]> result = new ArrayList<>();
        for (int[] ints : intervals) {
            //如果已经有区间值，并且当前值的开始值小于前一个区间的结束值，则有重叠，合并区间
            int size = result.size();
            if (size > 0 && ints[0] <= result.get(size - 1)[1]) {
                result.set(size - 1, new int[]{result.get(size - 1)[0], Math.max(result.get(size - 1)[1], ints[1])});
            } else {
                //无重叠直接放进去
                result.add(ints);
            }
        }

        return result.toArray(new int[result.size()][]);
    }
}
